package sort

import (
	"fmt"
)

// 获取待排序数组中的最大值
func getMax(a []int) int {
	max := a[0]
	for i := 1; i < len(a); i++ {
		if a[i] > max {
			max = a[i]
		}
	}
	return max
}

// 简单桶排序 ~=计数排序
func BucketSortSimple(source []int, n int) {
	if n <= 1 {
		return
	}
	array := make([]int, getMax(source)+1)
	for i := 0; i < len(source); i++ {
		array[source[i]]++
	}
	// 每个分数的数量
	fmt.Println(array)
	c := make([]int, 0)
	for i := 0; i < len(array); i++ {
		for array[i] != 0 {
			c = append(c, i)
			array[i]--
		}
	}
	copy(source, c)
}

func BucketSort(a []int, n int) {
	if n <= 1 {
		return
	}
	max := getMax(a)
	buckets := make([][]int, max+1)

	index := 0
	for i := 0; i < n; i++ {
		index = a[i]                                  // 数组i的值就是桶的编号
		buckets[index] = append(buckets[index], a[i]) // 加入对应的桶中
	}
	fmt.Println(buckets)

	tmpPos := 0 // 标记数组的位置
	for i := 0; i < max; i++ {
		bucketLen := len(buckets[i])
		if bucketLen > 0 {
			//sort.Sort(sort.IntSlice(buckets[i])) // 桶内快速排序
			copy(a[tmpPos:], buckets[i])
			tmpPos += bucketLen
		}
	}
}
